package com.chj.gaoji.class14;

//https://leetcode-cn.com/problems/count-of-range-sum/solution/327qu-jian-he-de-ge-shu-ti-jie-zong-he-by-xu-yuan-/
//https://leetcode-cn.com/problems/count-of-range-sum/solution/327qu-jian-he-de-ge-shu-ti-jie-zong-he-by-xu-yuan-/
public class Code07_CountofRangeSum {

	public int countRangeSum(int[] nums, int lower, int upper) {

		if (nums.length == 0) {
			return 0;
		}

		long[] prefix = new long[nums.length + 1];
		for (int i = 1; i < prefix.length; i++) {
			prefix[i] = prefix[i - 1] + nums[i - 1];
		}

		return mergeSort(prefix, 0, prefix.length - 1, lower, upper);
	}

	public int mergeSort(long[] nums, int left, int right, int lower, int upper) {
		if (left == right) {
			return 0;
		}

		int mid = left + ((right - left) >> 1);
		return mergeSort(nums, left, mid, lower, upper) + mergeSort(nums, mid + 1, right, lower, upper)
				+ mergeArr(nums, left, mid, right, lower, upper);
	}

	public int mergeArr(long[] nums, int left, int mid, int right, int lower, int upper) {

		int res = 0;
		// 计算部分
		int lowerIndex = mid + 1;
		int upperIndex = mid + 1;
		for (int i = left; i <= mid; i++) {
//			相当于nums[lowerIndex] - nums[i] >=  lower的个数
			while (lowerIndex <= right && nums[lowerIndex] - nums[i] < lower) {
				lowerIndex++;
			}
			while (upperIndex <= right && nums[upperIndex] - nums[i] <= upper) {
				upperIndex++;
			}
			res += upperIndex - lowerIndex;
		}

		long[] help = new long[right - left + 1];
		int i = 0;
		int p1 = left;
		int p2 = mid + 1;
		while (p1 <= mid && p2 <= right) {
			help[i++] = nums[p1] <= nums[p2] ? nums[p1++] : nums[p2++];
		}
		while (p1 <= mid) {
			help[i++] = nums[p1++];
		}
		while (p2 <= right) {
			help[i++] = nums[p2++];
		}
		for (i = 0; i < help.length; i++) {
			nums[left + i] = help[i];
		}

		return res;
	}

	public static void main(String[] args) {
//		System.out.println(4 <= 4 ? 7 : 8);
//		{
//			int[] nums = { -2, 5, -1 };
//			int lower = -2, upper = 2;
//
//			Code07_CountofRangeSum code03_CountofRangeSum = new Code07_CountofRangeSum();
//
//			System.out.println(code03_CountofRangeSum.countRangeSum(nums, lower, upper));
//		}

//		[2147483647,-2147483648,-1,0]
//				-1
//				0
//		输出：
//		3
//		预期：
//        4
		{
			int[] nums = { 2147483647, -2147483648, -1, 0 };
			int lower = -1, upper = 0;

			Code07_CountofRangeSum code03_CountofRangeSum = new Code07_CountofRangeSum();

			System.out.println(code03_CountofRangeSum.countRangeSum(nums, lower, upper));
		}
	}
}
